package 困难.树;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
 * 实现 WordFilter 类：
 * WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
 * f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 
 * 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。
 * 如果不存在这样的单词，返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/prefix-and-suffix-search
 */
public class 前缀和后缀搜索_745 {

    public static void main(String[] args) {

        String[] words = {"apple"};
        WordFilter wordFilter = new WordFilter(words);
        System.out.println(wordFilter.f("a", "le"));

    }

    /**
     * 字典树
     * 使用两颗字典树，分别存储 顺序字符串，逆序字符串
     * 前缀在顺序字典树中查找，后缀在逆序字典树中查找
     * 注意:
     * 每个节点需要用一个列表存储 字符串 所在的索引
     * 前缀查找返回的 索引集 和 后缀查找返回的 索引集 的 交集，即为符合条件的字符串
     * 优先选择索引较大的字符串，可以将前缀的索引用 哈希表 存储起来，后缀的索引用
     * 链表 存储，链表时有序的，里面的索引是从小到大排序，逆序遍历，如果存在于前缀的索引集
     * 中返回该索引
     */
    static class WordFilter {

        private Tree prefixTree = new Tree();

        private Tree suffixTree = new Tree();

        public WordFilter(String[] words) {
            for (int i = 0; i < words.length; i++) {
                prefixTree.insertPref(words[i], i);
                suffixTree.insertSuff(words[i], i);
            }
        }

        public int f(String pref, String suff) {
            Set<Integer> prefIds = prefixTree.findPref(pref);
            if (prefIds.size() == 0) return -1;
            List<Integer> suffIds = suffixTree.findSuff(suff);
            for (int i = suffIds.size() - 1; i >= 0; i--) {
                if (prefIds.contains(suffIds.get(i))) {
                    return suffIds.get(i);
                }
            }
            return -1;
        }

        static class Tree {

            private List<Integer> listIds;

            private Set<Integer> setIds;

            private Tree[] child = new Tree[26];

            public void insertPref(String str, int index) {
                Tree curNode = this;
                for (int i = 0; i < str.length(); i++) {
                    int curIdx = str.charAt(i) - 'a';
                    if (curNode.child[curIdx] == null) {
                        curNode.child[curIdx] = new Tree();
                        curNode.child[curIdx].setIds = new HashSet<>();
                    }
                    curNode.child[curIdx].setIds.add(index);
                    curNode = curNode.child[curIdx];
                }
            }

            public void insertSuff(String str, int index) {
                Tree curNode = this;
                for (int i = str.length() - 1; i >= 0; i--) {
                    int curIdx = str.charAt(i) - 'a';
                    if (curNode.child[curIdx] == null) {
                        curNode.child[curIdx] = new Tree();
                        curNode.child[curIdx].listIds = new ArrayList<>();
                    }
                    curNode.child[curIdx].listIds.add(index);
                    curNode = curNode.child[curIdx];
                }
            }

            public Set<Integer> findPref(String str) {
                Tree curNode = this;
                for (int i = 0; i < str.length(); i++) {
                    int curIdx = str.charAt(i) - 'a';
                    if (curNode.child[curIdx] == null) {
                        return new HashSet<>();
                    }
                    curNode = curNode.child[curIdx];
                }
                return curNode.setIds;
            }

            public List<Integer> findSuff(String str) {
                Tree curNode = this;
                for (int i = str.length() - 1; i >= 0; i--) {
                    int curIdx = str.charAt(i) - 'a';
                    if (curNode.child[curIdx] == null) {
                        return new ArrayList<>();
                    }
                    curNode = curNode.child[curIdx];
                }
                return curNode.listIds;
            }
        }
    }
}


